package com.ling.dataStructures.trie;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

/**
 * @author: ling007
 * @date: 2025/2/10 16:56
 * @description: Trie 字典树
 */

public class Trie {

    public final static TrieNode wordsTree = new TrieNode();


    /**
     * 插入一个单词
     * @param word 单词
     * @param explain 说明
     */
    public void insert(String word, String explain){
        TrieNode root = wordsTree;
        char[] charArray = word.toCharArray(); //将单词转换为字符数组
        for (char c : charArray) {
            int idx = c - 'a'; //获取字符在数组中的位置(- a 从 0 开始，参考 ASCII 码表)
            if (root.slot[idx] == null){
                root.slot[idx] = new TrieNode();
            }
            root = root.slot[idx];
            root.c = c;
            root.prefix++;
        }
        root.isWord = true; //标注是一个单词
        root.explain = explain;  //循环拆解后，最后一个字符就是单词的结束字符
    }


    public List<String> searchPrefix(String prefix){
        ArrayList<String> list = new ArrayList<>();
        TrieNode root = wordsTree;
        char[] charArray = prefix.toCharArray();

        StringBuilder cache = new StringBuilder();
        //精准匹配，根据前置查找前面的单词
        for (char c : charArray) {
            int idx = c - 'a';
            if (idx > wordsTree.slot.length || idx < 0 ||root.slot[idx] == null){
                return Collections.emptyList();
            }
            cache.append(c);
            root = root.slot[idx];
        }
        //模糊匹配，找出所有符合的单词
        if (root.prefix != 0) {
            for (int i = 0; i < root.slot.length; i++) {
                if (root.slot[i] != null) {
                    list.add(cache.append(root.slot[i].c).toString());
                    char c = (char) (i + 'a');
                    collect(root.slot[i], String.valueOf(cache) + c, list, 15);
                    if (list.size() >= 15) {
                        return list;
                    }
                }
            }
        }



        return list;
    }


    protected void collect(TrieNode trieNode, String pre, List<String> queue, int resultLimit) {
        // 找到单词
        if (trieNode.isWord) {
            trieNode.word = pre;
            // 保存检索到的单词到 queue
            queue.add(trieNode.word + " -> " + trieNode.explain);
            if (queue.size() >= resultLimit) {
                return;
            }
        }
        // 递归调用，查找单词
        for (int i = 0; i < trieNode.slot.length; i++) {
            char c = (char) ('a' + i);
            if (trieNode.slot[i] != null) {
                collect(trieNode.slot[i], pre + c, queue, resultLimit);
            }
        }
    }

    @Override
    public String toString() {
        return "Trie：" + JSON.toJSONString(wordsTree);
    }
}
